/// 计算找零时所需的最小纸币数，使用贪心算法选择最大面额的纸币来实现最优解
///
/// # 参数
/// - `amount`: 需要找零的金额
///
/// # 返回
/// 返回所需的最小纸币数量
pub fn dp_rec_mc(amount: u32) -> u32 {
    // 定义可用的纸币面额，从大到小排列
    let denominations = [100, 50, 30, 20, 10, 5, 2, 1];
    // 初始化纸币数量计数器
    let mut count = 0;
    // 剩余需要找零的金额，初始值为输入的金额
    let mut remaining = amount;

    // 遍历所有纸币面额
    for &denomination in &denominations {
        // 当剩余金额大于或等于当前纸币面额时，继续使用该面额纸币
        while remaining >= denomination {
            // 减少剩余金额
            remaining -= denomination;
            // 增加纸币计数
            count += 1;
        }
    }

    // 返回所需的最小纸币数量
    count
}

// 在最小找零问题中，贪心算法并不总是能够得到最优解。
// 但本题中，由于纸币的面额是普遍使用并经过合理设计的，贪心算法可以得到最优解。
// 证明：假设存在一个最优解，使用了比贪心更多的纸币数量，那么可以通过替换其中的多个小纸币为更大面额的纸币，得到一个更优解。